#include <bits/stdc++.h>

using namespace std;

int exgcd(int a,int b,int &x,int &y){
    if(b){
        int r=exgcd(b,a%b,x,y);
        int t=x;
        x=y;
        y=t-a/b*y;
        return r;
    }else{
        x=1;y=0;
        return a;
    }
}

bool linearEqu(int a,int b,int c,int &x,int &y){
    int r=exgcd(a,b,x,y);
    if(c%r) return false;
    int t=c/r;
    x*=t;y*=t;
    //x+=b/r;
    //y-=a/r;
    return false;
}
